Rotated digits [Memoization]

Time: O(LogN); Space: O(LogN); easy

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X.

Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation.

  • 0, 1, and 8 rotate to themselves;

  • 2 and 5 rotate to each other (on this case they are rotated in a different direction, in other words 2 or 5 gets mirrored);

  • 6 and 9 rotate to each other, and

  • the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

Example 1:

Input: 10

Output: 4

Explanation:

  • There are four good numbers in the range [1, 10] : 2, 5, 6, 9.

  • Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Example 2:

Input: 5

Output: 2

Explanation:

  • There are two good numbers in the range [1, 5] : 2, 5.

Constraint:

  • N will be in range [1, 10000]

1. Dynamic Programming [O(LogN), O(LogN)]

[1]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(LogN)
    """
    def rotatedDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        A = list(map(int, str(N)))
        invalid, diff = set([3, 4, 7]), set([2, 5, 6, 9])

        def dp(A, i, is_prefix_equal, is_good, lookup):
            if i == len(A): return int(is_good)
            if (i, is_prefix_equal, is_good) not in lookup:
                result = 0
                for d in range(A[i]+1 if is_prefix_equal else 10):
                    if d in invalid:
                        continue
                    result += dp(A, i+1,
                                 is_prefix_equal and d == A[i],
                                 is_good or d in diff,
                                 lookup)
                lookup[i, is_prefix_equal, is_good] = result
            return lookup[i, is_prefix_equal, is_good]

        lookup = {}

        return dp(A, 0, True, False, lookup)

[2]:

s = Solution1()
N = 10
assert s.rotatedDigits(N) == 4
N = 5
assert s.rotatedDigits(N) == 2

2. Dynamic Programming [O(LogN), O(LogN)]

[3]:

class Solution2(object):
    def rotatedDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        INVALID, SAME, DIFF = 0, 1, 2
        same, diff = [0, 1, 8], [2, 5, 6, 9]
        dp = [0] * (N+1)
        dp[0] = SAME

        for i in range(N//10+1):
            if dp[i] != INVALID:
                for j in same:
                    if i*10+j <= N:
                        dp[i*10+j] = max(SAME, dp[i])
                for j in diff:
                    if i*10+j <= N:
                        dp[i*10+j] = DIFF

        return dp.count(DIFF)

[4]:

s = Solution2()
N = 10
assert s.rotatedDigits(N) == 4
N = 5
assert s.rotatedDigits(N) == 2

3. Dynamic Programming [O(LogN), O(LogN)]

[5]:

class Solution3(object):
    def rotatedDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        invalid, diff = set(['3', '4', '7']), set(['2', '5', '6', '9'])
        result = 0

        for i in range(N+1):
            lookup = set(list(str(i)))
            if invalid & lookup:
                continue
            if diff & lookup:
                result += 1

        return result

[6]:

s = Solution3()
N = 10
assert s.rotatedDigits(N) == 4
N = 5
assert s.rotatedDigits(N) == 2